
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        /**
 * 
 输入：
 let arr = [
    {id: 1, name: '部门1', pid: 0},
    {id: 2, name: '部门2', pid: 1},
    {id: 3, name: '部门3', pid: 1},
    {id: 4, name: '部门4', pid: 3},
    {id: 5, name: '部门5', pid: 4},
]
输出：
[
    {
        "id": 1,
        "name": "部门1",
        "pid": 0,
        "children": [
            {
                "id": 2,
                "name": "部门2",
                "pid": 1,
                "children": []
            },
            {
                "id": 3,
                "name": "部门3",
                "pid": 1,
                "children": [
                    {
                        "id": 4,
                        "name": "部门4",
                        "pid": 3,
                        "children": [
                            {
                                "id": 5,
                                "name": "部门5",
                                "pid": 4,
                                "children": []
                            }
                        ]
                    }
                ]
            }
        ]
    }
]


 * 
 */

/* 

总结：
数组转树形解构
有2类解法
一种是循环
    可以根据当前元素找子级，然后把子级的元素存到当前的children里面
    可以根据当前元素找父级，然后再把元素存到父级的children
     优化版可以借助map
一种是递归
 */

// 问题：要是arr顺序变了就无法找到父级
function arrToTree(arr){
    // 把当前元素缓存到map，然后当查找父元素的时候，会把当前元素拿到并且修改
    let map=new Map();
    let res=[];
    for (let index = 0; index < arr.length; index++) {
        const element = arr[index];
        // 把当前元素保存到map
        map.set(element.id,element)

        // 从map获取父级元素
        const parent=map.get(element.pid)
       if(parent){
            if(parent.children){
                parent.children.push(element)
            }else{
                parent.children=[element]
            }
       }
 
    }
    console.dir(arr,map)
    return map.get(1)
}


//先把元素缓存在map里面，这样就可以避免先后顺序问题
function arrToTree2(arr){
    // 把当前元素缓存到map，然后当查找父元素的时候，会把当前元素拿到并且修改
    let map=new Map();
    let res=[];
    
//     for (let index = 0; index < arr.length; index++) {
//         const element = arr[index];
//         element.children=[]
//         // 把当前元素保存到map
//         map.set(element.id,element)
//    }
//先把元素存放在map里
   arr.forEach(element=>{
    map.set(element.id,element)
   })
    for (let index = 0; index < arr.length; index++) {
       
        const element = arr[index];
        //只保存pid为零的结果到res集合里就好了
        if(element.pid===0){
            res.push(element)
        }else{
              // 从map获取父级元素
            const parent=map.get(element.pid)
            if(parent){
                    if(parent.children){
                        parent.children.push(element)
                    }else{
                        parent.children=[element]
                    }
            }
        }   
      
 
    }
    console.dir(arr,map)
    return res
}


    </script>

    <script>
        //方法1：循环查找子集元素，然后放到当前元素的children里面
        //方法2： 循环查找父级元素，然后把当前元素放到父级元素的children里面
        // 双循环实现，历遍每一个，然后在每个里面去找它的子集
        function arrToTree3(arr){
            let res=[]
            for (let index = 0; index < arr.length; index++) {
                const element = arr[index];
                element.children=findChildren(arr,element.id)
                if(element.pid===0){
                    res=[element]
                }
            }
            return res
        }
        function findChildren(arr,id=0){
            let res=[]
            for (let index = 0; index < arr.length; index++) {
                const element = arr[index];
                if(id===element.pid){
                    res.push(element)
                }
            }
            return res;
        }

        // 等同于
        function arrToTree31(arr){
            let res=[]
            for (let index = 0; index < arr.length; index++) {
                const element = arr[index];
                // 查找当前元素的子级元素，并且存放在当前元素的children里面
                element.children=arr.filter(item=>item.pid===element.id)
                if(element.pid===0){
                    res.push(element)
                }
                
            }
            return res
        }

        //方法2： 循环查找父级元素，然后把当前元素放到父级元素的children里面
        function arrToTree32(arr){
            let res=[]
            for (let index = 0; index < arr.length; index++) {
                const element = arr[index];
               
                if(element.pid===0){
                    res.push(element)
                }else{
                     // 查找当前元素的子级元素，并且存放在当前元素的children里面
                    const parent=arr.find(item=>item.id===element.pid)
                    if(parent){
                        if(parent.children){
                            parent.children.push(element)
                        }else{
                            parent.children=[element]
                        }
                    }
                }
                
            }
            return res
        }

            // id为7就会在结果集里面丢失，因为没有找到对应的父级。
        console.log(arrToTree31([
        {id: 1, name: '部门1', pid: 0},
        {id: 2, name: '部门2', pid: 1},
        {id: 3, name: '部门3', pid: 1},
        {id: 4, name: '部门4', pid: 3},
        {id: 5, name: '部门5', pid: 4},
        {id: 7, name: '部门5', pid: 6},
       
        
    ]))

    </script>

<script>

    // 递归方式
    function arrToTree4(arr){
        let res=[]
        findChildren(arr,0,res)
        return res
    }
    function findChildren(arr,pid=0,res){
       
        for (let index = 0; index < arr.length; index++) {
            console.log('count')
            const element = arr[index];
            if(pid===element.pid){
                    element.children=[];
                    res.push(element)
                    findChildren(arr,element.id,element.children)
            }
            
        }
        
    }

//     console.log(arrToTree4([

// {id: 2, name: '部门2', pid: 1},
// {id: 3, name: '部门3', pid: 1},
// {id: 4, name: '部门4', pid: 3},
// {id: 5, name: '部门5', pid: 4},
// {id: 7, name: '部门5', pid: 6},
// {id: 1, name: '部门1', pid: 0},

// ]))

</script>
</body>
</html>
